window.onload = function () {
    /**
     * 77. 组合
     */
    console.log(combine(4, 2))

    /**
     * 46. 全排列
     */
    console.log(permute([1,2,3]))

    /**
     * 47. 全排列 II
     */
    console.log(permuteUnique([1,1,2]))
}

/**
 * 77. 组合
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
    const ans = [];
    const dfs = (cur, n, k, temp) => {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.length + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.length == k) {
            ans.push(temp);
            return;
        }
        // 考虑选择当前位置
        dfs(cur + 1, n, k, [...temp, cur]);
        // 考虑不选择当前位置
        dfs(cur + 1, n, k, temp);
    }
    dfs(1, n, k, []);
    return ans;
};

/**
 * 46. 全排列
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;

    function backtracking(n, k, used) {
        if (path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++) {
            if (used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

/**
 * 47. 全排列 II
 * @param {number[]} nums
 * @return {number[][]}
 */
 var permuteUnique = function(nums) {
    nums.sort((a, b) => {
            return a - b
        })
        let result = []
        let path = []
    
        function backtracing( used) {
            if (path.length === nums.length) {
                result.push(path.slice())
                return
            }
            for (let i = 0; i < nums.length; i++) {
                if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                    continue
                }
                if (!used[i]) {
                    used[i] = true
                    path.push(nums[i])
                    backtracing(used)
                    path.pop()
                    used[i] = false
                }
    
    
            }
        }
        backtracing([])
        return result
    };